/*
https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode-soluti-f7uh/
 */
public class Solution518 {
    public int change(int amount, int[] coins) {
        int[] f=new int[amount+1];
        f[0]=1;
        for (int coin : coins) {
            for (int i=1;i<=amount;i++){
                if (i>=coin){
                    f[i]+=f[i-coin];
                }
            }
        }
        return f[amount];
    }

    public static void main(String[] args) {
        System.out.println(new Solution518().change(5,new int[]{1,2,5}));
    }
}
